package 双指针;

import com.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*力扣15题
* 给一个整数数组nums，判断是否存在三元组[nums[i],nums[j],nums[k]]
* 满足 i !=j,i!=k且j！=k,同时 还满足 nums[i]+nums[j]+nums[k] == 0
* 请你返回所有和为0且不重复的三元组
* 答案中不可以包含重复的三元组，顺序忽略*/
/*思路：排序+双指针
* 1.排序，2.固定一个数a  3.在该数后面的区间内，利用双指针算法，快速找到两个和等于 -a即可*/
/*细节：1.去重： 找到结果之后，left 与 right 指针要跳过重复的元素
*       每次使用完一次双指针算法之后，i也需要跳过重复元素
*      2. 不漏： 找到结果后不要停，缩小区间继续寻找*/
public class 三数之和 {



    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();


        Arrays.sort(nums);
        int n = nums.length;
        if(nums ==null || n<3){
            return ret;
        }
        for(int i=0;i<n;){//固定数

            if(nums[i]>0) break; //优化时间

            int left=i+1,right=n-1;
            int target = -nums[i];

            while(left<right){
                int sum = nums[left]+nums[right];

                if(sum>target) right--;
                else if(sum<target) left++;
                else{
                    ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));
                    left++;
                    right--;
                    //去重
                    while(left<right && nums[left]==nums[left-1]) left++;
                    while(left<right && nums[right]==nums[right+1]) right--;
                }

            }
            i++;
            while(i<n&&nums[i]==nums[i-1]) i++; //去重

        }
        return ret;
    }

    public static void main(String[] args) {
        int [] nums={0,0,0};

        threeSum(nums);



    }
}
